// https://www.lintcode.com/problem/maximum-swap/ 

// O(N3)
// class Solution {
// public:
//     /**
//      * @param num: a non-negative intege
//      * @return: the maximum valued number
//      */
//     int maximumSwap(int num) {
//         int max_var = 0;
//         int num_size = 0;
//         vector<int> num_var;
//         int tmp_num = num;
//         while (tmp_num)
//         {
//             num_var.push_back(tmp_num % 10);
//             tmp_num /= 10;
//             num_size += 1;
//         }
//         if (num_size <= 1) return num;
//         for (int i = 0; i < num_size; ++i)
//         {
//             for (int j = i + 1; j < num_size; ++j)
//             {
//                 swap(num_var[i], num_var[j]);
//                 int tmp = 0;
//                 for (int t = 0; t < num_var.size(); ++t)
//                 {
//                     tmp += num_var[t] * pow(10, t);
//                 }
//                 max_var = max(max_var, tmp); 
//                 swap(num_var[i], num_var[j]);
//             }
//         }
//         return max_var;
//     }
// };




// O(N)
class Solution {
public:
    /**
     * @param num: a non-negative intege
     * @return: the maximum valued number
     */
    int maximumSwap(int num) {
        vector<int> max_var;
        vector<int> max_idx;
        int num_size = 0;
        vector<int> num_var;
        int tmp_num = num;
        while (tmp_num)
        {
            int tmp_var = tmp_num % 10;
            num_var.push_back(tmp_var);
            if (max_var.empty()) 
            {
                max_var.push_back(tmp_var);
                max_idx.push_back(0);
            }
            else if (tmp_var > max_var.back())
            {
                max_var.push_back(tmp_var);
                max_idx.push_back(num_var.size() - 1);
            } 
            else
            {
                max_var.push_back(max_var.back());
                max_idx.push_back(max_idx.back());
            }
            tmp_num /= 10;
            num_size += 1;
        }
        for (int i = num_var.size() - 1; i >= 0; --i)
        {
            if (num_var[i] < max_var[i])
            {
                swap(num_var[i], num_var[max_idx[i]]);
                break;
            }
        }
        int result = 0;
        for (int i = 0; i < num_var.size(); ++i)
        {
            result += num_var[i] * pow(10, i);
        }
        return result;
    }
};